package 力扣算法练习.main1.part2;

import java.util.*;

public class day22 {
    /*
    给出集合[1,2,3,...,n]，其所有元素共有n! 种排列。
    按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
    给定n 和k，返回第k个排列。
    https://leetcode.cn/problems/permutation-sequence
     */
    //执行代码时正确的但是点提交代码时虽然是同一个测试用例但是结果是错的
    StringBuilder result=new StringBuilder();
    public static int count=0;
    boolean flag1=false;
    public String getPermutation(int n, int k) {
        boolean[]flag=new boolean[n];
        Deque<Integer> temp=new ArrayDeque<>();
        int step=0;
        runGet(flag,k,temp,step);
        return result.toString();
    }
    private void runGet(boolean[] flag,int k,Deque<Integer> temp,int step){
        if (step==flag.length){
            count++;
            return;
        }
        for (int i = 0; i <flag.length ; i++) {
            if (flag[i])continue;//已经排序了的数
            temp.addLast(i+1);
            flag[i]=true;
            runGet(flag,k,temp,step+1);
            if (flag1)return;
            if (count==k){
                for(int s:temp){
                    result.append(s);
                }
                flag1=true;
                return;
            }
            temp.removeLast();
            flag[i]=false;
        }
    }
    //官方解
    public String getPermutation1(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        --k;
        StringBuffer ans = new StringBuffer();
        int[] valid = new int[n + 1];
        Arrays.fill(valid, 1);
        for (int i = 1; i <= n; ++i) {
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; ++j) {
                order -= valid[j];
                if (order == 0) {
                    ans.append(j);
                    valid[j] = 0;
                    break;
                }
            }
            k %= factorial[n - i];
        }
        return ans.toString();
    }

}
